//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "type_traits.h"
#include "iterator_traits.h"
#include "memory.h"


FC_NAMESPACE_BEGIN


template <class T> inline
	const T& max( const T& a, const T& b )
	{
		return a > b ? a : b;
	}

template <class T> inline
	const T& min( const T& a, const T& b )
	{
		return a < b ? a : b;
	}

template <class T> inline
	void fast_clamp( T& t, const T& low, const T& high )
	{
		if( t < low ) t = low;
		else if( t > high ) t = high;
	}

template <class T> inline
	T clamp( T t, T low, T high )
	{
		if( t < low ) t = low;
		else if( t > high ) t = high;
		return t;
	}

template <class T> inline
	void swap( T& a, T& b )
	{
		T temp(a);
		a = b;
		b = temp;
	}

template <class InputIterator> FC_FORCE_INLINE
	void iter_swap( InputIterator a, InputIterator b )
	{
		swap(*a, *b);
	}


// swap_ranges

template <class T> inline
	void swap_ranges( T* first, T* last, T* result )
	{
		for( ; first != last; ++result, ++first )
			swap(*first, *result);
	}


// clamp_range

template <class ForwardIterator, class T> inline
	void clamp_range( ForwardIterator first, ForwardIterator last, const T& low, const T& high )
	{
		for( ; first != last; ++first )
			fast_clamp( *first, low, high );
	}



namespace internal
{

	template <class Iter, class T> FC_FORCE_INLINE
		T* copy( Iter first, Iter last, T* result, true_type )
		{
			return (T*)mem_copy( (void*)first, (void*)last, (void*)result );
		}

	template <class InputIterator, class OutputIterator> inline
		OutputIterator copy( InputIterator first, InputIterator last, OutputIterator result, false_type )
		{
			for( ; first != last; ++result, ++first )
				*result = *first;
			return result;
		}

	template <class Iter, class T> FC_FORCE_INLINE
		T* reverse_copy( Iter first, Iter last, T* result, true_type )
		{
			return (T*)mem_move( (void*)first, (void*)last, (void*)result );
		}

	template <class BidirectionalIterator, class OutputIterator> inline
		OutputIterator reverse_copy( BidirectionalIterator first, BidirectionalIterator last, OutputIterator result, false_type )
		{
			for( ; first != last; ++result )
				*result = *--last;
			return result;
		}

	template <class Iter, class T> FC_FORCE_INLINE
		T* copy_backward( Iter first, Iter last, T* result, true_type )
		{
			ptrdiff_t n = ptrdiff_t(last - first);
			return (T*)((char*)mem_move( (void*)first, (void*)last, (void*)(result - n) ) - n);
		}

	template <class Iter1, class Iter2> inline
		Iter2 copy_backward( Iter1 first, Iter1 last, Iter2 result, false_type )
		{
			while( last != first )
				*(--result) = *(--last);
			return result;
		}

	template<class Iter, class T> inline
		T* copy_n( Iter first, size_t n, T* result, true_type )
		{
			if( n > 0 )
				::memcpy( (void*)result, (void*)first, n * sizeof(T) );
			return (result + n);
		}

	template<class Iter, class T> inline
		T* copy_n( Iter first, size_t n, T* result, false_type )
		{
			for( ; n != 0; ++result, ++first )
				*result = *first, --n;
			return result;
		}

	template <class Iter, class T> inline
		void fill( Iter first, Iter last, const T& value, true_type )
		{
			::memset( (void*)first, (int)value, size_t((const char*)last - (const char*)first) );
		}

	template <class Iter, class T> inline
		void fill( Iter first, Iter last, const T& value, false_type )
		{
			for( ; first != last; ++first )
				*first = value;
		}

	template <class Iter, class T> inline
		Iter fill_n( Iter first, size_t n, const T& value, true_type )
		{
			::memset( (void*)first, (int)value, n );
			return first + n;
		}

	template <class Iter, class T> inline
		Iter fill_n( Iter first, size_t n, const T& value, false_type )
		{
			while( n-- )
				*first++ = value;
			return first;
		}

} //internal


// copy

template <class InputIterator, class OutputIterator> FC_FORCE_INLINE
	OutputIterator copy( InputIterator first, InputIterator last, OutputIterator result )
	{
		return internal::copy( first, last, result, typename is_binary_copyable<
			is_pointer<InputIterator>::value, is_pointer<OutputIterator>::value,
				has_trivial_assign< typename iterator_traits<InputIterator>::value_type >::value,
				has_trivial_assign< typename iterator_traits<OutputIterator>::value_type >::value
			>::type()
		);
	}


// reverse_copy

template <class BidirectionalIterator, class OutputIterator> FC_FORCE_INLINE
	OutputIterator reverse_copy( BidirectionalIterator first, BidirectionalIterator last, OutputIterator result )
	{
		return internal::reverse_copy( first, last, result, typename is_binary_copyable<
			is_pointer<BidirectionalIterator>::value, is_pointer<OutputIterator>::value,
				has_trivial_assign< typename iterator_traits<BidirectionalIterator>::value_type >::value,
				has_trivial_assign< typename iterator_traits<OutputIterator>::value_type >::value
			>::type()
		);
	}


// copy_backward

template <class InputIterator, class OutputIterator> FC_FORCE_INLINE
	OutputIterator copy_backward( InputIterator first, InputIterator last, OutputIterator result )
	{
		return internal::copy_backward( first, last, result, typename is_binary_copyable<
				is_pointer<InputIterator>::value, is_pointer<OutputIterator>::value,
				has_trivial_assign< typename iterator_traits<InputIterator>::value_type >::value,
				has_trivial_assign< typename iterator_traits<OutputIterator>::value_type >::value
			>::type()
		);
	}


// copy_n

template<class InputIterator, class OutputIterator> FC_FORCE_INLINE
	OutputIterator copy_n( InputIterator first, size_t n, OutputIterator result )
	{
		return internal::copy_n( first, n, result, typename is_binary_copyable<
				is_pointer<InputIterator>::value, is_pointer<OutputIterator>::value,
				has_trivial_assign< typename iterator_traits<InputIterator>::value_type >::value,
				has_trivial_assign< typename iterator_traits<OutputIterator>::value_type >::value
			>::type()
		);
	}


// fill

template <class ForwardIterator, class T> FC_FORCE_INLINE
	void fill( ForwardIterator first, ForwardIterator last, const T& value )
	{
		return internal::fill( first, last, value, typename is_binary_copyable<
				is_pointer<ForwardIterator>::value,
				is_sizeof< typename iterator_traits<ForwardIterator>::value_type, 1 >::value
			>::type()
		);
	}

// fill_n

template <class ForwardIterator, class T> FC_FORCE_INLINE
	ForwardIterator fill_n( ForwardIterator first, size_t n, const T& value )
	{
		return internal::fill_n( first, n, value, typename is_binary_copyable<
				is_pointer<ForwardIterator>::value,
				is_sizeof< typename iterator_traits<ForwardIterator>::value_type, 1 >::value
			>::type()
		);
	}


// find

template <class ForwardIterator, class T> FC_FORCE_INLINE //inline
	ForwardIterator find( ForwardIterator first, ForwardIterator last, const T& value )
	{
		while( (first != last) && !(*first == value) )
			++first;
		return first;
	}


// find_if

template <class InputIterator, class UnaryPredicate> inline
	InputIterator find_if( InputIterator first, InputIterator last, UnaryPredicate predicate )
	{
		for( ; first != last ; ++first )
			if( predicate(*first) )
				break;
		return first;
	}


// reverse_find

template <class BidirectionalIterator, class T> inline
	BidirectionalIterator reverse_find( BidirectionalIterator first, BidirectionalIterator last, const T& value )
	{
		BidirectionalIterator last2 = last;
		if( FC_LIKELY(first != last) )
		{
			for( --first, --last; (first != last) && !(*last == value); --last )
				;
		}
		return (last == first) ? last2 : last;
	}


// lexicographical_compare

template <class InputIterator1, class InputIterator2, class Compare> inline
	bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2, Compare compare )
	{
		for( ; first1 != last1 && first2 != last2; first1++, first2++ )
		{
			if( compare(*first1, *first2) ) return true;
			if( compare(*first2, *first1) ) return false;
		}
		return (first1 == last1) && (first2 != last2);
	}

inline bool lexicographical_compare( const char* first1, const char* last1, const char* first2, const char* last2 )
	{
		ptrdiff_t a(last1 - first1), b(last2 - first2);
		int result = ::memcmp( first1, first2, (a < b ? a : b) );
		return result ? (result < 0) : (a < b);
	}

namespace internal
{

	template <class InputIterator1, class InputIterator2> FC_FORCE_INLINE
		bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1,
		InputIterator2 first2, InputIterator2 last2, false_type )
		{
			return fc::lexicographical_compare( first1, last1, first2, last2,
				less< typename iterator_traits<InputIterator1>::value_type >() );
		}

	template <class InputIterator1, class InputIterator2> FC_FORCE_INLINE
		bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1,
		InputIterator2 first2, InputIterator2 last2, true_type )
		{
			return fc::lexicographical_compare((const char*)first1, (const char*)last1,
				(const char*)first2, (const char*)last2 );
		}
}

template <class InputIterator1, class InputIterator2> inline
	bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2 )
	{
		return internal::lexicographical_compare( first1, last1, first2, last2, typename is_binary_comparable<
				is_pointer<InputIterator1>::value, is_pointer<InputIterator2>::value,
				is_sizeof< typename iterator_traits<InputIterator1>::value_type, 1 >::value,
				is_sizeof< typename iterator_traits<InputIterator2>::value_type, 1 >::value
			>::type()
		);
	}


// Container algorithms
template <class Container, class T> inline
	bool contains( const Container& c, const T& value )
	{
		return find( c.begin(), c.end(), value ) != c.end();
	}



FC_NAMESPACE_END

